超限归纳法()是数学归纳法向(大)良序集合比如基数或序数的集合的扩展。
超限归纳假设只要对于所有的 β < α,P(β) 为真,则 P(α) 也为真。那么超限归纳告诉我们 P 对于所有序数为真。
就是说,如果 P(α) 为真只要 P(β) 对于所有 β < α 为真,则 P(α) 对于所有 α 为真。或者更实用的说:若要证明所有序数 α 都符合性质 P,你可以假定它对于所有更小的 β < α 已经是成立的。
通常证明被分为三种情况:
零情况: 证明 P(0) 为真。后继情况: 证明对于任何后继序数 β+1, P(β+1) 得出自 P(β)(如果需要的话,也假定对于所有 α < β 有 P(α))。极限情况: 证明对于任何极限序数 λ, P(λ) 得出自 [P(α) 对于所有 α < λ]。留意,以上三種情況(證明方法)都是相同的,只是所考虑的序数类型不同。正式來說不用分开考慮它们,但在实践時,因為它们的证明過程通常相差很大,所以需要分别表述。在一些情況下,「零情況」會被視為一種「極限情況」,因此可以使用極限序數來證明。
超限递归超限递归是一種构造或定义某种對象的方法,它與超限归纳的概念密切相關。例如,可以定義以序數為下標的集合序列 Aα ,只要指定三个事項:
A0 是什么如何确定 Aα+1 自 Aα(又或者是從A0到 Aα的部分)对于极限序数 λ,如何确定 Aλ 自 Aα 的对于 α < λ 的序列。更形式的说,我们陈述超限递归定理如下。给定函数类 G1, G2, G3,存在一个唯一的超限序列 F 带有 dom(F) = Ord {\displaystyle Ord} (Ord {\displaystyle Ord}是所有序数的真类),使得
F(0) = G1(∅ {\displaystyle \emptyset } )F(α+1 {\displaystyle \alpha +1} ) = G2(F(α {\displaystyle \alpha } )),对于所有 α∈Ord {\displaystyle \alpha \in Ord} F(α {\displaystyle \alpha } ) = G3(F ↾α {\displaystyle \upharpoonright \alpha } ),对于所有极限序數 α≠0 {\displaystyle \alpha \neq 0} 。這裡的F ↾α {\displaystyle \upharpoonright \alpha } 是指F 在 {β∈Ord:β